#include <stdio.h>
#include <stdlib.h>
#define MAX(A, B) ((A) > (B) ? (A) : (B))
typedef struct AVL
{
    int data;
    int high;
    struct AVL *left, *right;
};
int high(AVL *node)
{

    if (!node)
        return 0;
    return node->high;
}
void LL_rotation(AVL *&A)
{
    AVL *B = A->left;
    A->left = B->right;
    B->right = A;
    // alter high!!!
    A->high = MAX(high(A->left), high(A->right)) + 1;
    B->high = MAX(high(B->left), high(B->right)) + 1;
    A = B;
}
void RR_rotation(AVL *&A)
{
    AVL *B = A->right;
    A->right = B->left;
    B->left = A;
    // alter high!!!
    A->high = MAX(high(A->left), high(A->right)) + 1;
    B->high = MAX(high(B->left), high(B->right)) + 1;
    A = B;
}
void LR_rotation(AVL *&A)
{
    RR_rotation(A->left);
    LL_rotation(A);
}

void RL_rotation(AVL *&A)
{
    LL_rotation(A->right);
    RR_rotation(A);
}
void insert(AVL *&root, int key)
{
    if (!root)
    {
        root = (AVL *)malloc(sizeof(AVL));
        root->data = key;
        root->left = root->right = NULL;
        root->high = 0;
    }
    else
    {
        if (root->data > key)
        { //left insert
            insert(root->left, key);
            if (high(root->left) - high(root->right) >= 2)
            {
                if (key < (root->left)->data)
                {
                    LL_rotation(root);
                }
                else if (key > (root->left)->data)
                {
                    LR_rotation(root);
                }
            }
        }
        else if (root->data < key)
        { //right insert
            insert(root->right, key);
            if (high(root->right) - high(root->left) >= 2)
            {
                if (key > (root->right)->data)
                {
                    RR_rotation(root);
                }
                else if (key < (root->right)->data)
                {
                    RL_rotation(root);
                }
            }
        }
    }
    root->high = MAX(high(root->left), high(root->right));
}
void create_tree(AVL *&tree, int a[], int n)
{
    tree = NULL;
    for (int i = 0; i < n; i++)
    {
        insert(tree, a[i]);
    }
}
void midorder_transverval(AVL *root)
{
    if (root)
    {
        midorder_transverval(root->left);
        printf("%4d", root->data);
        midorder_transverval(root->right);
    }
}
int main()
{
    /*******************code*******************/

    int a[] = {34, 23, 15, 98, 115, 28, 107};
    // int a[] = {34, 34, 34, 34, 34, 34, 34};
    AVL *tree;
    create_tree(tree, a, 7);
    midorder_transverval(tree);
    /******************************************/
    printf("\n\n****************************\n");
    printf("Press Enter key to continue\n");
    getchar();
    return 0;
    /******************************************/
}
